{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:35:34.361375Z",
     "start_time": "2018-12-18T07:35:34.341817Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Authorization for Minor Form.rtf\n",
      "child_wishlist_v2.csv\n",
      "gift_goodkids_v2.csv\n",
      "sample_submission_random_v2.csv\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "import math\n",
    "from collections import Counter\n",
    "from subprocess import check_output\n",
    "#看看文件是否存在，并且是不是用utf8\n",
    "print(check_output([\"ls\", \"input\"]).decode(\"utf8\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 后面看懂代码后改成dataframe\n",
    "```python\n",
    "drop(0,1)的意思是：其中1表示axis=1,0表示名称，在这里即为删除名称为0的列\n",
    "gift_pref_df = pd.read_csv('../input/child_wishlist_v2.csv',header=None).drop(0,1)\n",
    "child_pref_df = pd.read_csv('../input/gift_goodkids_v2.csv',header=None).drop(0,1)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:36:12.769168Z",
     "start_time": "2018-12-18T07:35:50.404791Z"
    }
   },
   "outputs": [],
   "source": [
    "#居然转换成了ndarry\n",
    "#孩子喜欢的礼物\n",
    "gift_pref = pd.read_csv('input/child_wishlist_v2.csv',header=None).drop(0, 1).values\n",
    "#礼物喜欢的孩子\n",
    "child_pref = pd.read_csv('input/gift_goodkids_v2.csv',header=None).drop(0, 1).values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:40:45.064798Z",
     "start_time": "2018-12-18T07:40:45.044964Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "numpy.ndarray"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(child_pref)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:41:43.919580Z",
     "start_time": "2018-12-18T07:41:43.670798Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "999\n"
     ]
    }
   ],
   "source": [
    "print(np.min(gift_pref))\n",
    "print(np.max(gift_pref))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:41:58.341740Z",
     "start_time": "2018-12-18T07:41:58.333955Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "999999\n"
     ]
    }
   ],
   "source": [
    "print(np.min(child_pref))\n",
    "print(np.max(child_pref))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-17T14:18:41.581930Z",
     "start_time": "2018-12-17T14:18:41.571474Z"
    }
   },
   "outputs": [],
   "source": [
    "#有1000000个children\n",
    "n_children = 1000000 \n",
    "#1000种gift\n",
    "n_gift_type = 1000\n",
    "#每种gift1000个\n",
    "n_gift_quantity = 1000 \n",
    "#每个孩子有喜欢的100个礼物。(孩子开心)\n",
    "n_gift_pref = 100 # number of gifts a child ranks\n",
    "#每个礼物优先考虑1000个好孩子（圣诞老人开心）\n",
    "n_child_pref = 1000 # number of children a gift ranks\n",
    "#0-5000为三胞胎，triplets=50001 0.5%\n",
    "triplets = math.ceil(0.005 * n_children / 3.) * 3    \n",
    "#5001-45000双胞胎，即45000-5001+1=40000\n",
    "twins = math.ceil(0.04 * n_children / 2.) * 2    \n",
    "#根据目标函数里面定义的\n",
    "ratio_gift_happiness = 2\n",
    "ratio_child_happiness = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.构造child偏好列表和gift编号列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:43:37.221038Z",
     "start_time": "2018-12-18T07:43:37.209698Z"
    }
   },
   "outputs": [],
   "source": [
    "#非双胞胎和非三胞胎的孩子，因为成pair，因此-6只是占位符\n",
    "class Child(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer):\n",
    "        # 每个孩子有自己的ID和prefer列表，这里使用字典来存储prefer列表中的giftID和对应的happiness，\n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        # 这里的happiness使用包含两个值的列表存储，前者是礼物为此giftID的happiness，后者是礼物不在prefer列表的happiness\n",
    "        for i in range(prefer.shape[0]):\n",
    "            self.prefer_dict[prefer[i]] = [12*(prefer.shape[0] - i), -6]\n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        # 添加gift对child的prefer，前者为孩子对礼物的happiness，后者对礼物对孩子的happiness\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 6*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 6*score] \n",
    "        return None\n",
    "        \n",
    "    def happiness(self, giftid):\n",
    "        # 获取当前childID和指定giftID的happiness对\n",
    "        # 若giftID不在prefer字典中，则返回[-6,-6]\n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:44:10.751795Z",
     "start_time": "2018-12-18T07:44:10.741279Z"
    }
   },
   "outputs": [],
   "source": [
    "#双胞胎\n",
    "class Child_twin(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer1, prefer2):\n",
    "        # 构造twins的prefer字典，用giftID在两个prefer列表中的score之和的三倍（平均score的6倍）和-6作为value\n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        \n",
    "        for p in list(set(list(prefer1) + list(prefer2))):\n",
    "            score = 0\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            self.prefer_dict[p] = [3*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        # 添加gift对child的prefer，前者为孩子对礼物的happiness，后者对礼物对孩子的happiness\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 3*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 3*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:44:38.886948Z",
     "start_time": "2018-12-18T07:44:38.874772Z"
    }
   },
   "outputs": [],
   "source": [
    "#三胞胎\n",
    "class Child_triplet(object):\n",
    "\"\"\"\n",
    "对于三胞胎，三个人要作为整体考虑\n",
    "param idx:child id \n",
    "param prefer1:三胞胎中第一个孩子偏爱的礼物\n",
    "param prefer2:三胞胎中第二个孩子偏爱的礼物\n",
    "param prefer3:三胞胎中第三个孩子偏爱的礼物\n",
    "\"\"\"\n",
    "    def __init__(self, idx, prefer1, prefer2, prefer3):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        #三胞胎三个人，有三组不同的喜欢的礼物，所以对于三胞胎set(list(prefer1) + list(prefer2) + list(prefer3))肯定大于100\n",
    "        for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):\n",
    "            score = 0\n",
    "            #对于三胞胎中的第一个人，偏爱有各种礼物的得分\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第二个人\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第三个人\n",
    "            if p in list(prefer3):\n",
    "                score += 2*(100 - list(prefer3).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #这个是在干啥？\n",
    "            # 使用三胞胎的平均score作为每个人的score\n",
    "            self.prefer_dict[p] = [2*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        # 添加gift对child的prefer，前者为孩子对礼物的happiness，后者对礼物对孩子的happiness\n",
    "        # 向字典中添加礼物对孩子的偏好得分\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 2*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 2*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:46:37.304188Z",
     "start_time": "2018-12-18T07:46:37.297973Z"
    }
   },
   "source": [
    "#### 得到一个孩子喜欢的礼物\n",
    "gift_pref[index]\n",
    "#### 三胞胎孩子的礼物\n",
    "Child_triplet(0, gift_pref[0], gift_pref[1], gift_pref[2])\n",
    "#### 双胞胎孩子的礼物\n",
    "Child_twin(5001, gift_pref[5001], gift_pref[5002])\n",
    "#### 普通孩子\n",
    "Child(45001, gift_pref[45001])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T08:18:35.781770Z",
     "start_time": "2018-12-18T08:18:35.752136Z"
    }
   },
   "source": [
    "### 小例子解释作者是在干啥\n",
    "```python\n",
    "C=[]\n",
    "C.append(Child_triplet(0, gift_pref[0], gift_pref[1], gift_pref[2]))\n",
    "C.append(Child_twin(5001, gift_pref[5001], gift_pref[5002]))\n",
    "C.append(Child(45001, gift_pref[45001]))\n",
    "\n",
    "#由于index=0的孩子是三胞胎，因此它偏爱的礼物数是大于100的,从下面的几个条语句可以看出，0号孩子也有偏爱0号礼物的。\n",
    "#虽然它不在0号孩子偏爱的礼物中，但它在1号孩子偏爱的礼物中。\n",
    "print(np.where(gift_pref[0]==0))\n",
    "print(np.where(gift_pref[1]==0))\n",
    "print(gift_pref[1][40])\n",
    "print(np.where(gift_pref[2]==0))\n",
    "(array([], dtype=int64),)\n",
    "(array([40]),)\n",
    "0\n",
    "(array([], dtype=int64),)\n",
    "#第0个孩子匹配第0个礼物的得分（这样存储的有个问题如果没有礼物则会直接报错）\n",
    "C[0].prefer_dict[0]\n",
    "[236, -6]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T09:43:55.201729Z",
     "start_time": "2018-12-18T09:17:16.783719Z"
    }
   },
   "outputs": [],
   "source": [
    "# 构造孩子的偏好列表及其匹配礼物的happiness\n",
    "Children = []\n",
    "for i in range(0, 5001, 3):\n",
    "    Children.append(Child_triplet(i, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+1, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+2, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "for i in range(5001, 45001, 2):\n",
    "    Children.append(Child_twin(i, gift_pref[i], gift_pref[i+1]))\n",
    "    Children.append(Child_twin(i+1, gift_pref[i], gift_pref[i+1]))\n",
    "Children = Children + [Child(i, gift_pref[i]) for i in range(45001, 1000000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T11:02:24.811192Z",
     "start_time": "2018-12-18T10:10:51.516511Z"
    }
   },
   "outputs": [],
   "source": [
    "for j in range(1000):# 遍历所有的giftID\n",
    "    #每类礼物更偏爱的孩子\n",
    "    cf = child_pref[j]\n",
    "    done_list = []\n",
    "    for i in range(cf.shape[0]):# 遍历一个giftID下所有的preferred kid ID\n",
    "        #同一礼物如果是三胞胎则以三胞胎中最先出现的为主。\n",
    "        # 如果是三胞胎中的一个，而且没有被处理，就一次性处理三胞胎\n",
    "        if cf[i] <= 5000 and cf[i] not in done_list:\n",
    "            if cf[i] % 3 == 0:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                cid3 = cf[i] + 2\n",
    "                done_list.append(cid2)\n",
    "                done_list.append(cid3)\n",
    "            elif cf[i] % 3 == 1:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                cid3 = cf[i] + 1\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid3)\n",
    "            else:\n",
    "                cid1 = cf[i] - 2\n",
    "                cid2 = cf[i] - 1\n",
    "                cid3 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid2)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            if cid3 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid3))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            # 将礼物对于孩子的偏好信息填入字典\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            Children[cid3].add_gifts_prefer(j, score_)\n",
    "        #如果是双胞胎，以双胞胎最先出现的为主\n",
    "        # 如果是twins中的childID，而且没有被处理，就一次性处理twins\n",
    "        elif cf[i] <= 45000 and cf[i] not in done_list:\n",
    "            if cf[i] % 2 == 1:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                done_list.append(cid2)\n",
    "            else:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            # 将礼物对于孩子的偏好信息填入字典\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            #如果是普通孩子\n",
    "        elif cf[i] > 45000:\n",
    "            Children[cf[i]].add_gifts_prefer(j, 2*(cf.shape[0] - i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 上述过程利用孩子的prefer列表和gift的prefer列表，为每一个孩子构造了一个偏好字典,key是giftID，value是[孩子对gift的happiness，gift对孩子的happiness]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.构建最小花费流模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 这里将孩子和礼物的一一配对问题抽象为将1,000,000个礼物分发给1,000,000个孩子的最小花费流问题。\n",
    "- 我们需要将礼物分发为孩子，每个礼物和孩子之间理论上都有一条通路，通路的容量为1，表示一个礼物只能分发给一个孩子；同时每条通路都有一个cost，我们需要找到cost最小的分发方式。\n",
    "- 通路的cost需要从这条通路连接的孩子和礼物的happiness来计算得到。\n",
    "- 此外还有一些限制条件，三胞胎、双胞胎需要一样的礼物；每种礼物只有一千个。\n",
    "- 三胞胎和双胞胎需要一样的礼物：通过定义从礼物到孩子的分发过程实现，在礼物分发的过程中，将三胞胎、双胞胎视为一个节点，即只给一个节点分发礼物，容量设为3、2，cost如何计算？\n",
    "- 每种礼物的数量可以通过设定节点的供应量supply来限制，将孩子节点的supply设为-1，表示需要1个礼物；将每种礼物结点的supply设为1000，表示只有1000个礼物，保证了整个网络的supply之和为0；此外还可以设立一些中转结点，supply=0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.graph import pywrapgraph\n",
    "# 最终happiness计算中的权重\n",
    "W_CHILD = 1\n",
    "W_GIFTS = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T11:27:46.657457Z",
     "start_time": "2018-12-18T11:27:46.649506Z"
    }
   },
   "outputs": [],
   "source": [
    "min_cost_flow = pywrapgraph.SimpleMinCostFlow()\n",
    "# 这里将孩子和礼物的\n",
    "# 开始结点，这里为礼物ID，取值为1000000-1000999\n",
    "start_nodes = []\n",
    "# 结束结点，这里为孩子ID，取值为0-999999\n",
    "end_nodes = []\n",
    "# 两个节点之间线路的容量，这里为从礼物结点到孩子结点可分发的礼物数量，由于三胞胎和双胞胎分发礼物时只给第一个孩子分发，\n",
    "# 所以三胞胎可分发礼物为3，双胞胎为2，其他人为1\n",
    "capacities = []\n",
    "# 单位花费，指从开始结点到结束结点分发一次礼物的cost，由于是最小花费流问题，\n",
    "# 这里为一次礼物分发过程（即礼物和孩子配对过程）的孩子happiness和礼物happiness的加权求和的负值\n",
    "unit_costs = []\n",
    "# 注意：这里的开始结点、结束结点、容量、单位花费的列表长度相等，元素是一一对应的，"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1.定义网络结构（包括开始结点、结束结点、边容量、单位花费）\n",
    "\n",
    "# triplets\n",
    "# 对于三胞胎的第一个孩子，对于其喜好列表中的每一个礼物，添加从礼物到孩子的网络通路（包括容量3和花费）\n",
    "for i in range(0, 5001, 3):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(3)\n",
    "        # 权重为什么是10000和0，为什么要加6？为了防止有负数？\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# twins\n",
    "# 对于双胞胎的第一个孩子，对于其喜好列表中的每一个礼物，添加从礼物到孩子的网络通路（包括容量2和花费）\n",
    "for i in range(5001, 45001, 2):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(2)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "# 对于其他的每一个孩子，对于其喜好列表，添加从喜好列表中每一个礼物到此孩子的通路（包括容量1和花费）\n",
    "for i in range(45001, 1000000):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2.add Arc；在节点之间添加边\n",
    "\n",
    "# gift -> children；\n",
    "# 添加从礼物到孩子的分发花费\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "# 1001000结点为孩子节点的集合结点，添加从每个收到礼物的孩子结点到此节点的一条路径，容量为收到礼物的数量，花费为0\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "# 1001001结点为礼物结点的汇总节点，添加从每个礼物结点到汇总节点的容量为1000花费为0的通路\n",
    "for i in range(1000):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "# 添加从开始结点的汇总节点到结束结点的汇总节点的容量为1000000花费为0的通路\n",
    "min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(1001001), int(1001000), int(1000000), int(0)\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 返回值为arc的index，表示一共构造了这么多条边"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3.add Supply：设置结点supply供应量，结点供给量之和为0\n",
    "\n",
    "# 将每个礼物结点的供应量设为1000，表示供给结点\n",
    "for i in range(1000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(1000000+i), int(1000))\n",
    "\n",
    "# 设置孩子节点的供应量\n",
    "# 将单个孩子结点的供应量设置为0，相当于中转节点\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "# 将礼物结点汇总节点的供应量设置为0，为中转结点\n",
    "min_cost_flow_1.SetNodeSupply(int(1001001), int(0)) \n",
    "# 将孩子汇总节点的供应量设置为-1000000，表示需要1000000份礼物，为接收节点\n",
    "min_cost_flow_1.SetNodeSupply(int(1001000), int(-1000000)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 解决最小花费流问题\n",
    "min_cost_flow.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 孩子和礼物的配对情况，index为孩子ID，值为礼物ID\n",
    "assignment = [-1]*1000000\n",
    "# 记录收到不同礼物的twins\n",
    "twins_differ = []\n",
    "triplets_differ = []\n",
    "\n",
    "#for i in well_assigned:\n",
    "#    assignment[i] = assignment_0[i]\n",
    "\n",
    "for i in range(min_cost_flow.NumArcs()):\n",
    "    # 在所有边中，找出有流量的流向孩子结点的边\n",
    "    if min_cost_flow.Flow(i) != 0 and min_cost_flow.Head(i) < 1000000:\n",
    "        c = min_cost_flow.Head(i)\n",
    "        g = min_cost_flow.Tail(i)\n",
    "        f = min_cost_flow.Flow(i)\n",
    "        # 按照边指定配对情况，记录收到不同礼物的双胞胎\n",
    "        if c >= 45001:\n",
    "            assignment[c] = g - 1000000\n",
    "\n",
    "        elif c >= 5001:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    twins_differ.append([c, c+1])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "            elif f == 2:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "        else:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                elif assignment[c+1] == -1:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                else:\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 2:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 3:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "                assignment[c+2] = g - 1000000\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 根据配对情况表和孩子礼物偏好字典计算幸福感\n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 查看不满足条件的双胞胎数量\n",
    "len(twins_differ), len(triplets_differ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 查看不满足条件的双胞胎ID\n",
    "twins_differ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 查看不满足条件的三胞胎ID\n",
    "triplets_differ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 查看指定孩子的配对礼物\n",
    "assignment[34267], assignment[34268]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 设定指定孩子的配对礼物\n",
    "assignment[34267] = 207\n",
    "assignment[34268] = 207"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# well assigned twins and triplets\n",
    "well_assigned = []\n",
    "for i in range(0, 5001, 3):\n",
    "    if assignment[i] == assignment[i+1] and assignment[i] == assignment[i+2]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)\n",
    "        well_assigned.append(i+2)\n",
    "for i in range(5001, 45001, 2):\n",
    "    if assignment[i] == assignment[i+1]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)\n",
    "# 查看满足条件的双胞胎数量\n",
    "len(well_assigned)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Gifts_left = [1000 for _ in range(1000)]\n",
    "for i in well_assigned:\n",
    "    if assignment[i] != -1:\n",
    "        Gifts_left[assignment[i]] -= 1\n",
    "# 查看满足条件的礼物数量\n",
    "sum(Gifts_left)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.计算平均归一化幸福感"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T13:35:32.667949Z",
     "start_time": "2018-12-13T13:35:32.661343Z"
    }
   },
   "source": [
    "#### 求最大公约数math.gcd\n",
    "```python\n",
    "greatest common divisor of x and y\n",
    "math.gcd(319,377)\n",
    "29\n",
    "```\n",
    "- 最大公约数=A×B/最小公倍数,下面的函数实际上是求的最小公倍数\n",
    "```python\n",
    "def lcm(a, b):\n",
    "    \"\"\"Compute the lowest common multiple of a and b\"\"\"\n",
    "    # in case of large numbers, using floor division\n",
    "    return a * b // math.gcd(a, b)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T13:42:45.142980Z",
     "start_time": "2018-12-13T13:42:45.137651Z"
    }
   },
   "outputs": [],
   "source": [
    "def lcm(a, b):\n",
    "    \"\"\"Compute the lowest common multiple of a and b，求的是最小公倍数\"\"\"\n",
    "    # in case of large numbers, using floor division\n",
    "    return a * b // math.gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# kaggle给的计算平均归一化幸福感的函数\n",
    "def avg_normalized_happiness(pred, child_pref, gift_pref):\n",
    "    \n",
    "    # check if number of each gift exceeds n_gift_quantity\n",
    "    gift_counts = Counter(elem[1] for elem in pred)\n",
    "    for count in gift_counts.values():\n",
    "        assert count <= n_gift_quantity\n",
    "                \n",
    "    # check if triplets have the same gift\n",
    "    for t1 in np.arange(0,triplets,3):\n",
    "        triplet1 = pred[t1]\n",
    "        triplet2 = pred[t1+1]\n",
    "        triplet3 = pred[t1+2]\n",
    "        # print(t1, triplet1, triplet2, triplet3)\n",
    "        assert triplet1[1] == triplet1[1] and triplet2[1] == triplet3[1]\n",
    "                \n",
    "    # check if twins have the same gift\n",
    "    for t1 in np.arange(triplets,triplets+twins,2):\n",
    "        twin1 = pred[t1]\n",
    "        twin2 = pred[t1+1]\n",
    "        # print(t1)\n",
    "        assert twin1[1] == twin2[1]\n",
    "\n",
    "    max_child_happiness = n_gift_pref * ratio_child_happiness\n",
    "    max_gift_happiness = n_child_pref * ratio_gift_happiness\n",
    "    total_child_happiness = 0\n",
    "    total_gift_happiness = np.zeros(n_gift_type)\n",
    "    \n",
    "    for row in pred:\n",
    "        child_id = row[0]\n",
    "        gift_id = row[1]\n",
    "        \n",
    "        # check if child_id and gift_id exist\n",
    "        assert child_id < n_children\n",
    "        assert gift_id < n_gift_type\n",
    "        assert child_id >= 0 \n",
    "        assert gift_id >= 0\n",
    "        child_happiness = (n_gift_pref - np.where(gift_pref[child_id]==gift_id)[0]) * ratio_child_happiness\n",
    "        if not child_happiness:\n",
    "            child_happiness = -1\n",
    "\n",
    "        gift_happiness = ( n_child_pref - np.where(child_pref[gift_id]==child_id)[0]) * ratio_gift_happiness\n",
    "        if not gift_happiness:\n",
    "            gift_happiness = -1\n",
    "\n",
    "        total_child_happiness += child_happiness\n",
    "        total_gift_happiness[gift_id] += gift_happiness\n",
    "    \n",
    "    print('normalized child happiness=',float(total_child_happiness)/(float(n_children)*float(max_child_happiness)) , \\\n",
    "        ', normalized gift happiness',np.mean(total_gift_happiness) / float(max_gift_happiness*n_gift_quantity))\n",
    "\n",
    "    # to avoid float rounding error\n",
    "    # find common denominator\n",
    "    # NOTE: I used this code to experiment different parameters, so it was necessary to get the multiplier\n",
    "    # Note: You should hard-code the multipler to speed up, now that the parameters are finalized\n",
    "    denominator1 = n_children*max_child_happiness\n",
    "    denominator2 = n_gift_quantity*max_gift_happiness*n_gift_type\n",
    "    common_denom = lcm(denominator1, denominator2)\n",
    "    multiplier = common_denom / denominator1\n",
    "\n",
    "    # # usually denom1 > demon2\n",
    "    return float(math.pow(total_child_happiness*multiplier,3) + math.pow(np.sum(total_gift_happiness),3)) / float(math.pow(common_denom,3))\n",
    "    # return math.pow(float(total_child_happiness)/(float(n_children)*float(max_child_happiness)),2) + math.pow(np.mean(total_gift_happiness) / float(max_gift_happiness*n_gift_quantity),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 计算给出的随机提交结果的幸福感\n",
    "random_sub = pd.read_csv('../input/sample_submission_random_v2.csv').values.tolist()\n",
    "print(avg_normalized_happiness(random_sub, child_pref, gift_pref))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- output:normalized child happiness= 0.04621203 , normalized gift happiness -4.59355e-05 9.868817990273061e-05"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
